package com.mdnote.practice.generic_recursion;

import java.util.LinkedList;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/15
 * @description 二叉树的最大深度
 */
public class LeetCode104 {

    public static void main(String[] args) {
        LeetCode104 leetCode104 = new LeetCode104();
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(15);
        root.left.left = new TreeNode(2);
        System.out.println(leetCode104.recursionOneLine(root));

    }

    public int maxDepth(TreeNode root) {
        // bfs
        forLoop(root);
        // recursion
        return recursion(root);
    }

    private int forLoop(TreeNode node) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        int left = 1;
        int right = 1;
        while (!queue.isEmpty()) {
            TreeNode tempNode = queue.removeFirst();
            if (tempNode.left != null) {
                left++;
                queue.addLast(tempNode.left);
            }
            if (tempNode.right != null) {
                right++;
                queue.addLast(tempNode.right);
            }
        }
        return Math.max(left, right);

    }

    public int recursion(TreeNode node) {
        // Terminator
        if (node.left == null && node.right == null) {
            return 1;
        }
        // process current data
        // drill down
        int max = 0;
        if (node.left != null) {
            max = recursion(node.left) + 1;
        } 
        if (node.right != null) {
            return Math.max(recursion(node.right) + 1, max);
        }
        return max;
        // restore current data
    }

    public int recursionOneLine(TreeNode node) {
        return Math.max(node.left != null ? recursionOneLine(node.left) : 0, node.right != null ? recursionOneLine(node.right) : 0) + 1;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
